import java.util.Stack;
public class PublicAncestor {
    public class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;
        public void TreeNode(char val) {
            this.val = val;
        }
    }
    public boolean getPath(TreeNode root,TreeNode node, Stack<TreeNode> stack) {
        if(root == null)
        {
            return false;
        }
        stack.push(root);
        if(root == node) {
            return true;
        }
        boolean flgleft = getPath(root.left,node,stack);
        if(flgleft) {
            return true;
        }
        boolean flgRight = getPath(root.right,node,stack);
        if(flgRight) {
            return true;
        }
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor2(TreeNode root,TreeNode p,TreeNode q) {
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root,p,stack1);
        getPath(root,q,stack2);
        int size1 = stack1.size();
        int size2 = stack2.size();
        if(size1 >size2) {
            int size = size1 - size2;
            while (size !=0) {
                stack1.pop();
                size--;
            }
        } else {
            int size = size2 - size1;
            while (size !=0) {
                stack2.pop();
                size--;
            }
        }
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            if (stack1.peek().equals(stack2.peek())) {

                return stack1.pop();
            }else {
                stack1.pop();
                stack2.pop();
            }
        }
        return null;
    }
}
